//矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2
//][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。 
//
// 给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
//输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]
// 
//
// 示例 2： 
//
// 
//输入：mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,2
//5,68,4],[84,28,14,11,5,50]]
//输出：[[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66]
//,[84,28,75,33,55,68]]
// 
//
// 
//
// 提示： 
//
// 
// m == mat.length 
// n == mat[i].length 
// 1 <= m, n <= 100 
// 1 <= mat[i][j] <= 100 
// 
// Related Topics 数组 矩阵 排序 
// 👍 60 👎 0


package leetcode.editor.cn.lc1329;

import java.util.Arrays;

public class SortTheMatrixDiagonally{
    public static void main(String[] args){
        Solution solution = new Solution();
    }
    


}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[][] diagonalSort(int[][] mat) {

        int m = mat.length;
        int n = mat[0].length;
        // 首行对角
        for (int r = 0, c = 0; c < n; c++) {
            int size = Math.min(m - r, n - c) - 1;
            if (size > 0) {
                sort(mat, r, c, r + size, c + size);
            }
        }
        //首列对角, 除第一行
        for (int r = 1, c = 0; r < m; r++) {
            int size = Math.min(m - r, n - c) - 1;
            if (size > 0) {
                sort(mat, r, c, r + size, c + size);
            }
        }


        return mat;
    }

    // 归并吧
    private void sort(int[][] mat, int r, int c, int maxr, int maxc) {
        int count = maxr - r + 1;
        if (count == 1) {
            return;
        } else if (count == 2) {
            swapIf(mat, r, c, maxr, maxc);
        } else {
            int mid = count >> 1;
            sort(mat, r, c, r + mid - 1, c + mid - 1);
            sort(mat, r + mid, c + mid, maxr, maxc);
            merge(mat, r, c, maxr, maxc, r + mid);
        }

    }

    private boolean swapIf(int[][] mat, int r, int c, int maxr, int maxc) {
        if (mat[r][c] > mat[maxr][maxc]) {
            int tmp = mat[r][c];
            mat[r][c] = mat[maxr][maxc];
            mat[maxr][maxc] = tmp;
            return true;
        }
        return false;
    }

    private void merge(int[][] mat, int r, int c, int maxr, int maxc, int mid) {
        int[] tmpArr = new int[maxr - r + 1];
        int index = 0;
        int delta = c - r;
        int i = r, j = mid;

        for (; i<mid || j<=maxr; ) {
            if (i >= mid) {
                tmpArr[index++] = mat[j][j + delta];
                j++;
            } else if (j > maxr) {
                tmpArr[index++] = mat[i][i + delta];
                i++;
            }else if (mat[i][i + delta] < mat[j][j + delta]){
                tmpArr[index++] = mat[i][i + delta];
                i++;
            }else {
                tmpArr[index++] = mat[j][j + delta];
                j++;
            }
        }
        System.out.print("merge tmp is :");
        System.out.println(Arrays.toString(tmpArr));
        for (int i1 = 0; i1 < tmpArr.length; i1++) {
            mat[r + i1][r + i1 + delta] = tmpArr[i1];
        }


    }

    //        private void swapRange(int[][] mat, int left, int index, int rightExclude, int delta) {
    //            int len = rightExclude - index;
    //
    //            for (int i = 0; i < len; i++) {
    //                int tail = rightExclude - i - 1;
    //                int tmp = mat[tail][tail + delta];
    //                for (int cur = tail; cur-len > left; cur-=len) {
    //                    mat[tail][tail + delta] = mat[tail - len][tail - len + delta];
    //                }
    //                mat[left + len - i][left + len - i + delta] = tmp;
    //            }
    //
    //
    //        }
}
//leetcode submit region end(Prohibit modification and deletion)